package com.bclz.datastructures

import scala.annotation.tailrec


object ListPractise {

  def addOneForAll(l:List[Int]):List[Int]= l match {
    case Nil => l
    case Cons(h,t)=>Cons(h+1,addOneForAll(t))
  }

  def double2String(l:List[Double]):List[String] = l match {
    case Nil => Nil
    case Cons(h,t)=>Cons(h.toString,double2String(t))
  }

  //非栈安全
  def map[A,B](as:List[A])(f:A=>B):List[B] = as match {

    case Nil => Nil
    case Cons(h,t)=>Cons(f(h),map(t)(f))

  }

  def map2[A,B](as:List[A])(f:A=>B):List[B] = {
    import scala.collection.mutable.ListBuffer
    val buf=new ListBuffer[B]
    @tailrec
    def mapRecursion(l:List[A]):List[B]={
      l match {
        case Nil => List(buf.toList:_*)
        case Cons(h,t)=>buf+=f(h); mapRecursion(t)

      }
    }
    mapRecursion(as)
  }

  def filter[A](as:List[A])(f:A=>Boolean):List[A]={

      import scala.collection.mutable.ListBuffer
      val buf=new ListBuffer[A]
      @tailrec
      def filter(l:List[A]):List[A]={

        l match {
          case Nil => List(buf.toList:_*)
          case Cons(h,t)=>if(f(h)) buf+=h;filter(t)
        }

      }
      filter(as)
  }

  def flatMap[A,B](l:List[A])(f:A=>List[B]):List[B]=List.concat(map(l)(f))

  def addTwoList(l1:List[Int],l2:List[Int]):List[Int]=(l1,l2) match {

    case (_,Nil) => Nil
    case (Nil,_) => Nil
    case (Cons(h1,t1),Cons(h2,t2))=>Cons(h1+h2,addTwoList(t1,t2))
  }

  def zipWith[A](l1:List[A],l2: List[A])(f:(A,A)=>A):List[A]=(l1,l2) match {
    case (_,Nil) => Nil
    case (Nil,_) => Nil
    case (Cons(h1,t1),Cons(h2,t2))=>Cons(f(h1,h2),zipWith(t1,t2)(f))
  }


  @tailrec
  def startWith[A](l:List[A],prefix:List[A]):Boolean= (l,prefix) match {

    case (Nil,_) => false
//    case (Cons(h1,t1),Cons(h2,t2)) =>{
//      if(h1==h2) startWith(t1,t2)
//      else false
//    }
    //这种写法比较好
    case (Cons(h1,t1),Cons(h2,t2))  if h1==h2 => startWith(t1,t2)
    case _ =>false
  }



  def hasSubSequence[A](sup:List[A],sub:List[A]):Boolean= sup match {
    case Nil =>false
    case _ if startWith(sup,sub) =>true
    case Cons(_,t) =>hasSubSequence(t,sub)
  }


  def main(args: Array[String]): Unit = {

      val l = List(1, 2, 3, 4, 5)
      println(addOneForAll(l))
      println(map2(l)(_+1))
      println(filter(l)(_==1))
      println(flatMap(l)(i=>List(i,i)))
  }
}
